package com.yuan.leetcode.JianZhiOffer;

/**
 * Created by yuanhaowu
 * Time 2022/6/10 21:39
 */
public class offer14_II {
    public int cuttingRope(int n) {
        if (n <= 3) {
            return n - 1;
        }
        int b = n % 3;
        long rem = 1, x = 3;
        for (int a = n / 3 - 1; a > 0; a /= 2) {
            if (a % 2 == 1) rem = (rem * x) % 1000000007;
            x = (x * x) % 1000000007;
        }
        if (b == 0) {
            return (int) (rem * 3 % 1000000007);
        }
        if (b == 1) {
            return (int) (rem * 4 % 1000000007);
        }
        return (int) (rem * 6 % 1000000007);
    }
}
